The described embodiments relate generally to storing streaming media, and more particularly to caching streaming media based on spatial locality and temporal locality of portions of media streams.
The sharing of videos having a variety of different content and encoded in different formats through video hosting services represents a growing need for effective organization, indexing and management. In the context of streaming electronic media, e.g., videos and audios, to viewers, there is some “locality” in streaming the requested media. For example, the same media streams or portions of a media stream are usually accessed multiple times in a given time period. Thus, caching streaming media, or maintaining temporary copies of media data locally, makes the media data more accessible by users compared to serving the streams from a central store. However, caching media data can be expensive because there may be multiple copies of the same media data cached to requesting users, and caches may reside in faster storage, which generally has a limited cache capacity. Thus, it is important to prioritize what data to put in the cache.
Many solutions are known for data caching in general, with particularly rich histories in computer processors (instruction and data caches) and operating systems (notably disk I/O and file systems. Particularly relevant to media caching is existing work on web proxies and Content Delivery Networks (CDNs). The most common caching algorithm is LRU (evict the Least Recently Used element). Other caching algorithms are typically described as variants of LRU, or at least compared with LRU. But the existing solutions face challenges to provide effective caching services. For example, most existing solutions fail to make full use of limited cache capacity, or fail to adapt to changes in user access patterns over time, or fail to use specific features of streaming media (e.g., popularity of a streaming media among multiple viewers) to improve caching performance.